#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <string>
#include <vector>

/*6
CN0010 BF0001
BF0001 AZ0001
AZ0001 NA
BF0010 AZ0001
AWO001 NA
BF0011 AZ0001
*/

// using namespace std;
// unordered_map<string, string> link;
// unordered_map<string, int> ver_count;

// int getDepth(const string& v) 
// {
// 	if (ver_count.find(v) != ver_count.end()) // 说明这个版本的深度已经计算过了
// 		return ver_count[v];
// 	// 走到这里说明没有计算过该版本的最大深度
// 	if (link.find(v) == link.end() || link[v] == "NA") // 当前版本没有出现，说明只有在父版本出现，为1；或者父版本为"NA"，那么也是1 
// 		ver_count[v] = 1;
// 	else
// 		ver_count[v] = 1 + getDepth(link[v]); // 说明有父版本，递归找父版本的深度

// 	return ver_count[v];
// }
// int main()
// {
// 	int N;
// 	cin >> N;
// 	// 构建了版本关系链和记录所有的版本
// 	unordered_set<string> ver;
// 	for (size_t i = 0; i < N; ++i)
// 	{
// 		string cur, prev;
// 		cin >> cur >> prev;
// 		link[cur] = prev;
// 		ver.insert(cur);
// 		if (prev != "NA")
// 			ver.insert(prev);
// 	}

// 	for (auto& v : ver)
// 	{
// 		getDepth(v);
// 	}

// 	// 找到最大深度
// 	int max_count = 0;
// 	for (auto& i : ver_count)
// 	{
// 		if (i.second > max_count)
// 			max_count = i.second;
// 	}

// 	// 遍历所有版本，找到最大深度的版本
// 	vector<string> result;
// 	for (auto& i : ver_count)
// 	{
// 		if (i.second == max_count)
// 			result.push_back(i.first);
// 	}

// 	sort(result.begin(), result.end());

// 	for (size_t i = 0; i < result.size(); ++i)
// 	{
// 		cout << result[i] << " ";
// 	}
// 	cout << endl;
// 	return 0;
// }


#include <map>
#include <climits>
#include <sstream>
using namespace std;

// map<char, vector<pair<char, int>>> graph;
unordered_map<char, vector<pair<char, int>>> graph;
string best_path;
int min_time = 0x3f3f3f3f;
void dfs(char start, char end, vector<char>& path, int time_spent, unordered_map<char, bool>& visited)
{
    if(start == end)
    {
        if(time_spent < min_time)
        {
            min_time = time_spent;
            best_path = "";
            for(auto& ch : path) best_path += ch;
        }
        return;
    }

    for(auto& neri : graph[start])
    {
        char next = neri.first;
        int cost = neri.second;
        if(visited[next] == false)
        {
            path.push_back(next);
            visited[next] = true;
            dfs(next, end, path, time_spent + cost, visited);
            path.pop_back();
            visited[next] = false;
        }
    }
}
int main()
{
    int N = 0;
    cin >> N;
    char start, end;
    cin >> start >> end;
    cin.ignore();
    string line;
    while(getline(cin, line))
    {
        if(line == "0000") break;

        stringstream ss(line);
        char u, v;
        int time;
        ss >> u >> v >> time;
        graph[u].push_back(make_pair(v, time));
        // graph[v].push_back(make_pair(u, time));
    }

    vector<char> path = {start};
    // map<char, bool> visited;
    unordered_map<char, bool> visited;
    visited[start] = true;

    dfs(start, end, path, 0, visited);

    for (char ch : best_path) cout << ch << " ";
    cout << endl;

    return 0;
}